from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def levelOrderBottom(root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """
    if not root:
        return []
    # res = []
    res = deque()
    q = deque()
    q.append(root)
    while len(q) > 0:
        temp = []
        size = len(q)
        while size > 0:
            cur = q.popleft()
            temp.append(cur.val)
            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)
            size -= 1
        res.insert(0, temp)
    return list(res)


root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(levelOrderBottom(root))
